
struct ListNode
{
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
 public:
  ListNode *mergeTwoLists(ListNode *list1, ListNode *list2)
  {
    ListNode *head, *run;
    if (list1 == nullptr)
      return list2;
    else if (list2 == nullptr)
      return list1;

    if (list1->val <= list2->val)
    {
      run = head = list1;
      list1 = list1->next;
    } else
    {
      head = run = list2;
      list2 = list2->next;
    }

    while (1)
    {
      if (list1 == nullptr)
      {
        run->next = list2;
        break;
      }
      if (list2 == nullptr)
      {
        run->next = list1;
        break;
      }
      if (list1->val <= list2->val)
      {
        run->next = list1;
        run = list1;
        list1 = list1->next;
      } else
      {
        run->next = list2;
        run = list2;
        list2 = list2->next;
      }
    }
    return head;
  }
};
